package LeetCode.month01.day15;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.List;

public class No23 {
    

//    按顺序，一个个进行两个有序链表的合并
    public ListNode merge(ListNode ans, ListNode listNode){
        if(ans==null||listNode==null)
            return ans==null?listNode:ans;
        ListNode head =new ListNode(0);
        ListNode curr = head;
        while(ans!=null&&listNode!=null){
            if(ans.val<listNode.val){
                curr.next = ans;
                curr = curr.next;
                ans = ans.next;
            }else{
                curr.next = listNode;
                curr = curr.next;
                listNode = listNode.next;
            }
        }
        if(ans!=null) curr.next=ans;
        if(listNode!=null) curr.next=listNode;
        return head.next;
    }

    public ListNode mergeKLists(ListNode[] lists) {
        ListNode ans = null;
        for (int i = 0; i < lists.length; i++) {
            ans = merge(ans,lists[i]);
        }
        return ans;


        //将所有链表中的数据取出来，排序再存放进链表中
//        ListNode head = new ListNode(-1);
//        ListNode curr = head;
//        List<Integer> list = new ArrayList<>();
//        for (ListNode list1 : lists) {
//            while(list1!=null){
//                list.add(list1.val);
//                list1 = list1.next;
//            }
//        }
//        Collections.sort(list);
//        for (Integer i : list) {
//            ListNode listNode = new ListNode(i);
//            curr.next = listNode;
//            curr=curr.next;
//        }
//        return head.next;
    }
}
